package demo8;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PowerSet {
    /**
     * n
     */
    public void simpleMethod(int[] arr) {
        int k=0;

        int length = 20;
        // 0
        // 4 * 5
        /** 0,1
         * 0,1 ..
         * 0,2 ..
         * 0,3 ..
         * 0,4 ..
         * 1,2 ..
         * 1,3 ..
         */
        // initial
        ArrayList<String> strings = new ArrayList<>();
        ArrayList<String> dest = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            strings.add(i + "");
        }
        dest.addAll(strings);
        ArrayList<String> strings2 = new ArrayList<>();
        /** time:
         * O(n^2) too slowly
         */
        while (true) {

            for (int i = 0; i < strings.size(); i++) {
                String s = strings.get(i);
                String[] split = strings.get(i).split(",");
                int start = Integer.parseInt(split[split.length - 1], 10);
                // start =1 i =1 and the j iterate
                for (int i1 = start; i1 < length; i1++) {
                    k++;
                    if (i1 + 1 == length) {
                        break;
                    }
                    // iterate the  arr
                    strings2.add(s + "," + (i1 + 1));
                }
            }
            dest.addAll(strings2);

            strings = strings2;
            if (strings2.get(0).split(",").length == length) break;
            strings2 = new ArrayList<>();
        }
        /**
         * 0,1,2,3
         * 0,1,2,4
         * when  the strings2.get(0) =arr.length ; stop it .
         * print ,and get the arr val
         */
        System.out.println("iterat count is : "+k);
        System.out.println("result count is : "+dest.size());
//        for (String s : dest) {
//            String[] split = s.split(",");
//            for (int i = 0; i < split.length; i++) {
//                System.out.print(arr[Integer.parseInt(split[i], 10)] + ",");
//            }
//            System.out.println();
//        }

    }

    public Recurison createPowerSetWithRecurison() {
        return new Recurison();
    }
    public RecurisonSameSpeed createPowerSetWithRecurisonSameSpeed() {
        return new RecurisonSameSpeed();
    }
    public class Recurison {
        private int count;
        /**
         * // get the (a,b) subSet
         * (a,b)  (a,b,c)
         */
        public void powsetInitAndStart(int[] arr) {
            ArrayList<String> arrayLists = new ArrayList<String>();
//            powset(arr, 0, arr.length - 1, arrayLists);
            powsetWithReturn(arr,0,arr.length-1,arrayLists);
            System.out.println("iterator count is "+count);
            System.out.println("result count is:  "+arrayLists.size());
//            for (String o : arrayLists) {
//                System.out.println(o.toString());
//            }
        }
// 120
        public void powset(int[] arr, int start, int end, ArrayList<String> beforeSequence) {
            // 0,3 =>(0,2)+3
            // 0,2 =>(0,1) +2
            // (0,1) => (0,0) +1
            if (start == end) {
                beforeSequence.add(start + "");
                return;
            }
            count++;
            // beforeSequence： [0,1]
            powset(arr, start, end - 1, beforeSequence);
            powset(arr, end, end, beforeSequence);

            // get the  sequence before or equal the s2
            int size = beforeSequence.size();
            for (int i = 0; i < size-1; i++) {
                beforeSequence.add(beforeSequence.get(i) + "," + end);
            }
            return;
        }
//374
        public ArrayList<String> powsetWithReturn(int[] arr, int start, int end, ArrayList<String> beforeSequence) {
            // 0,3 =>(0,2)+3
            // 0,2 =>(0,1) +2
            // (0,1) => (0,0) +1
            if (start == end) {
                beforeSequence.add(start + "");
                return beforeSequence ;
            }
// 2^n 2^11
            // beforeSequence： [0,1]
            ArrayList<String> beforeSequence1 = powsetWithReturn(arr, start, end - 1, beforeSequence);
            ArrayList<String> beforeSequence2= powsetWithReturn(arr, end, end, beforeSequence);
            count++;
            // get the  sequence before or equal the s2
            int size = beforeSequence1.size();
            for (int i = 0; i < size-1; i++) {
                beforeSequence1.add(beforeSequence1.get(i) + "," + end);
            }
            return beforeSequence1;
        }

        // arr[]: 0,1,2  0, 2
        public String powsetSimple(int[] arr, int start, int end) {
            if (start == end) {
                System.out.println(start);
                return start + "";
            }
            System.out.println(start + "," + end);
            // f(0,2) => [f(0,1),f(1,2)]
            String s1 = powsetSimple(arr, start, end - 1); //  0,1 -> 0,0   (0,1), (0)
            // f(1,3) => [f(1,2),f(2,3)]
            String s2 = powsetSimple(arr, start + 1, end); // 1,2 , 2,2   (1,2),(2)
            // f(0,3)=>[]
            System.out.println(s1 + "," + s2);
            return s1 + "," + s2;
            /**
             * 0,1
             * 0
             * 1
             */
            /**
             * 0,
             * 1,
             * 1,
             * 2
             * 0,1
             * 1,2
             * 0,1,1,2
             */
        }
    }
    public class RecurisonSameSpeed {
        private int count=0;
        public void powsetInitAndStart(int[] arr) {
            ArrayList<List<Integer>> lists = powsetWithReturn(0, arr);
            System.out.println("iterator count is "+count);
            System.out.println("result count is:  "+lists.size());

//            for (List o : lists) {
//                System.out.println(o.toString());
//            }
        }
        /**
         *  0
         *  1
         *  2 [] [2]
         */
        ArrayList allSequence =null;
        public ArrayList<List<Integer>> powsetWithReturn(int start,int[] initArray) {

            if(initArray.length==start){
                    allSequence = new ArrayList<List<Integer>>(){{
                    add(new ArrayList<>());
                }};
            }else{
                count++;
                ArrayList<List<Integer>> subSet = powsetWithReturn(start + 1, initArray);
                ArrayList<List<Integer>> moreSet = new  ArrayList<List<Integer>>();
                int item = initArray[start]; // 1
                int size = subSet.size();
                for (int i = 0; i <size;  i++) {

                    List<Integer> list = subSet.get(i);
                    ArrayList<Integer> integers = new ArrayList<>();
                    integers.addAll(list);
                    integers.add(item);
                    moreSet.add(integers);
                }
                allSequence.addAll(moreSet);
            }
            return allSequence;

        }

    }

    public void subSet() {


    }
}
